package cn.mengfly.algorithm.search;

/**
 * kmp 字符串搜索算法，搜索一个字符串在另一个字符串中的位置，算法复杂度O(n+m)
 * <p>
 * 参考连接：
 * <ol>
 *     <li><a href="https://www.zhihu.com/question/21923021">https://www.zhihu.com/question/21923021</a></li>
 *     <li><a href="http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html">http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html</a></li>
 * </ol>
 *
 * @author Mengfly
 * @date 2021/6/1 8:51
 */
public class KmpSearch {

    public static int search(String source, String target) {
        return search(source, target, 0);
    }

    public static int search(String source, String target, int startPos) {
        if (target.length() + startPos > source.length()) {
            return -1;
        }

        int tar = startPos, pos = 0;
        int length = source.length();

        int[] next = buildNext(target);

        while (tar < length) {
            if (source.charAt(tar) == target.charAt(pos)) {
                tar++;
                pos++;
            } else if (pos != 0) {
                pos = next[pos - 1];
            } else {
                tar++;
            }
            if (pos == target.length()) {
                return tar - pos;
            }
        }
        return -1;

    }

    /**
     * 最大前缀-后缀匹配字符数数组
     *
     * @param target 要构建最大匹配字符数数组的字符串
     * @return 最大前缀-后缀匹配字符数数组
     */
    private static int[] buildNext(String target) {
        int[] next = new int[target.length()];
        int i = 1, now = 0;
        while (i < target.length()) {
            if (target.charAt(i) == target.charAt(now)) {
                now++;
                next[i] = now;
                i++;
            } else if (now != 0) {
                now = next[now - 1];
            } else {
                next[i] = now;
                i++;
            }
        }
        return next;
    }
}
